#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#define RANKNUM 1000
#define DataFile "data.txt"

int save(int *arr);
int build_data();
int input_data();
int dijkstra(int **arr,int nodesNum,int startnode);         //Dijkstra algorithm
int floyd(int **arr,int nodesNum);                          //Floyd algorithm

int main()
{
    time_t m_start,m_end;
    m_start = clock();    //!< Time units are ms
    FILE *fp1;
    if ((fp1 = fopen(DataFile,"r")) == NULL)
    {
        printf("create test.txt \n");
        build_data();
    }
    fclose(fp1);
    input_data();
    m_end   = clock();
    printf("\n----------------main method run used %f ms------------\n",difftime(m_end,m_start));
    return 0;
}

int input_data(){
    int **Array;
    int x,i=0;
    int m=0,n=0;
    Array=(int **)malloc(RANKNUM*sizeof(int *));
    for(i=0;i<RANKNUM;i++){
        Array[i]=(int *)malloc(RANKNUM*sizeof(int));
    }
    FILE * fp_read;
    if ((fp_read = fopen(DataFile,"r")) == NULL)
    {
        printf("can not open input file \n");
        return 0;
    }
    /*get data from edgeWeight.text to initialize dynamic array "Array"*/
    while(fscanf(fp_read,"%d%*[^0-9]",&x)>0){
        if(n<RANKNUM){
            Array[m][n++]=x;
        }else{
            n=0;
            Array[++m][n++]=x;
        }
    }

    struct timeval start, end;
    long endusec;
    //double d_start,d_end;
    //double floyd_start,floyd_end;
    //nodesNum个节点(通过nodesNum即可控制读取节点数量)
    int nodesNum=500;
    //double duration;
    for(;nodesNum<=RANKNUM;nodesNum+=20){
        printf("nodesNum_%d\t",nodesNum);

        gettimeofday( &start, NULL );
        //d_start=clock();
        dijkstra(Array,nodesNum,0);
        //d_end=clock();
        gettimeofday( &end, NULL );

        if(end.tv_sec-start.tv_sec>0){
            x=end.tv_sec-start.tv_sec;
            //printf("----%d\t",x*1000000);
            endusec=end.tv_usec+x*1000000-start.tv_usec;
        }else{
            endusec=end.tv_usec-start.tv_usec;
        }

        printf("dijstra\t%ld\n",endusec);
        //printf("%ld\t%ld\t%ld\n",end.tv_sec-start.tv_sec,end.tv_usec,start.tv_usec);
        //printf("dijkstra\t%f\t",difftime(d_end,d_start));//CLOCKS_PER_SEC
/*
        floyd_start = clock();
        floyd(Array,nodesNum);
        floyd_end = clock();
        printf("floyd\t%f\n",difftime(floyd_end,floyd_start));
*/
    }

    fclose(fp_read);
    free(Array);
    return 0;
}

/**
* Dijkstra algorithm
*/
int dijkstra(int **arr,int nodesNum,int startnode){
    int distance[nodesNum];                 //存储起始节点到各点的距离
    int pred[nodesNum];                     //每个节点记录自己的前驱节点
    int visited[nodesNum];                  //记录节点访问信息（是否访问过）
    int i,count,mindistance,nextnode;

    //initialize pred[],distance[] and visited[]
    for(i=0;i<nodesNum;i++)
    {
        distance[i]=arr[startnode][i];      //当前起始节点到各点的距离
        pred[i]=startnode;                  //初始化访问节点
        visited[i]=0;                       //初始状态各节点都未访问过
    }

    distance[startnode]=0;                  //初始化起始节点到自己距离为0
    visited[startnode]=1;                   //标记第一个已访问节点为起始节点
    count=1;                                //节点遍历计数器

    while(count<nodesNum-1)
    {
        mindistance=1000000;
        //nextnode gives the node at minimum distance
        for(i=0;i<nodesNum;i++){                            //从未加入已找到最短路径集合的点里寻找起始节点到某一个节点的最短路径
            if(distance[i]<mindistance&&!visited[i])        //如果当前节点未曾被访问过，且起始节点到当前点 i 距离小于当前最新的最小距离，则更新最短距离为 startnode 到当前点 i 的距离
            {
                mindistance=distance[i];
                nextnode=i;
            }
        }

        //check if a better path exists through nextnode
        visited[nextnode]=1;
        for(i=0;i<nodesNum;i++){
            if(!visited[i]){
                if(mindistance+arr[nextnode][i]<distance[i])
                {
                    distance[i]=mindistance+arr[nextnode][i];
                    pred[i]=nextnode;
                }
            }

        }
        count++;
    }
//    //print the path and distance of each node
//    for(i=0;i<nodesNum;i++){
//        if(i!=startnode)
//        {
//            printf("\nDistance of node%d=%d",i,distance[i]);
//            printf("\nPath=%d",i);
//            j=i;
//            do
//            {
//                j=pred[j];
//                printf("<-%d",j);
//            }while(j!=startnode);
//        }
//    }
    return 0;
}

/**
* Floyd algorithm
*/
int floyd(int **arr,int nodesNum){
    int i,j,k;
    for (k=0;k<nodesNum;k++){
        for (i=0;i<nodesNum;i++){
            for (j=0;j<nodesNum;j++){
                if(arr[i][j]>arr[i][k]+arr[k][j]){
                    arr[i][j]=arr[i][k]+arr[k][j];
                }
            }
        }
    }
    return 0;
}

int save(int *arr)
{

    FILE *fp;
    int i=0;
    if ((fp=fopen(DataFile,"a"))==NULL) //打开只写的文本文件
    {
        printf("cannot open file!");
        exit(0);
    }
    for (i=0;i<RANKNUM;i++){
        fprintf(fp , "%d" , *(arr+i) );
        fputs(",",fp);
    }
    fputs("\n",fp);
    fclose(fp); //关文件
    return 0;
}

int build_data(){
    srand((unsigned)time(NULL));
    int temp = 0;
    int i,j=0;

    time_t c_start,c_end;
    c_start = clock();    //!<单位为ms

    int *arr;
    for (i = 0; i < RANKNUM; i++)
    {
        arr = (int *)malloc(RANKNUM * sizeof(int));     //动态申请一个100*4的空间
        for (j = 0; j < RANKNUM; j++)
        {
            if (i == j){
                arr[j]=0;
                continue;
            }
            temp = (rand() % (201));    //产生0~200之间的随机数
            if (temp>100){

                arr[j]=1000000;
            }
            else if (temp >= 5){
                arr[j]=temp;
            }
            else{
                arr[j]=0;
            }
        }
        save(arr);
        free(arr);
    }
    c_end   = clock();
    printf("crate datafile used %f ms \n",difftime(c_end,c_start));
    return 0;
}



